import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//二叉树节点类
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val = val;
    }
}

public class BinaryTreeLinked {
    //链式结构创建二叉树
    public static TreeNode createBinaryTreeLinked(){
        Scanner sc = new Scanner(System.in);  //创建一个Sc对象用于接收用户从控制台的输入
        System.out.println("请输入二叉树节点个数: ");
        int rootVal = sc.nextInt();  //将获取的节点个数存储在rootVal中
        TreeNode root = new TreeNode(rootVal);

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);  //将根节点的值放入到队列中

        while (!queue.isEmpty()){
            TreeNode currentNode = queue.poll();  //只要队列不为空，取出队列头部的节点作为当前节点currentNode
            System.out.printf("请输入节点%d的左子节点的值(如果没有则输入-1) : ",currentNode.val);
            int leftVal = sc.nextInt();

            if (leftVal!=-1){  //表示有左子节点或右子节点，就创建相应的节点，将其与当前节点建立链接，并把新建节点加入到队列中
                TreeNode leftNode = new TreeNode(leftVal);
                currentNode.left = leftNode;
                queue.add(leftNode);
            }

            System.out.printf("请输入节点%d的右子节点的值(如果没有则输入-1) : ",currentNode.val);
            int rightVal = sc.nextInt();
            if (rightVal!=-1){
                TreeNode rightNode = new TreeNode(rightVal);
                currentNode.right = rightNode;
                queue.add(rightNode);
            }
        }
        sc.close();

        return root;
    }


    //用于测试，以层序遍历方式输出二叉树
    public static void levelOrderTraversal(TreeNode root){
        if (root==null){
            return;  //直接返回，不进行任何操作
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode currentNode = queue.poll();  //只要队列不为空，取出队列头部的节点currentNode并输出其值

            System.out.println(currentNode.val+" ");
            if (currentNode.left!=null){  //如果当前节点有左子节点，就将左子节点加入到队列中
                queue.add(currentNode.left);
            }
            if (currentNode.right!=null){  //同理
                queue.add(currentNode.right);
            }
        }
    }

    public static void main(String[] args) {
        //调用createBinaryTreeLinked()方法创建链式结构二叉树得到根节点linkedTree
        TreeNode linkedTree = createBinaryTreeLinked();
        System.out.println("链式结构创建的二叉树，以层序遍历形式输出: ");
        levelOrderTraversal(linkedTree);
    }
}
